#include<stdio.h>

void Swap(int *a, int *b)
{
    int c=*a;
    *a=*b;
    *b=c;
}

void PrintArray(int *a,int size)
{
    for(int i=0; i<size; i++)
    {
        printf("%d ",a[i]);
    }
}
//冒泡排序
void BubbleSort(int *a,int size)
{
    for(int i=0; i<size-1; i++) //外循环代表 次数
    {
        int flag=0;
        for(int j=0; j<size-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                flag=1;
                Swap(&a[j],&a[j+1]);
            }
        }
        if(flag==0)  //数列已经有序
        break;
    }
}

//插入排序
void InsertSort(int *a, int size)
{
    for(int i=1; i<size; i++)  //要插入的数的下标
    {
        int j=i; //当前要插入的数的下标
        int temp= a[i]; //要插入的数的值
        for(; j>0; j--)
        {
            if(a[j-1]> temp)  //前面的这个数更大
            a[j]=a[j-1];
            else              //前面的数更小
            break;
        }
        a[j]=temp;
    }
}

void ChooseSort(int *a, int size)
{
    for(int i=0; i<size-1; i++)
    {
        int min=i;
        for(int j=i+1; j<size; j++)
        {
            if(a[min]>a[j])
            {
                min=j;
            }
        }
        Swap(&a[i],&a[min]);
    }
}

//双指针版本的选择排序
void ChooseSort2(int *a, int size)
{
    int left=0; //左指针
    int right=size-1; //右指针
    while (left< right)
    {
        int min= left;
        int max= right;
        for(int i=left; i<= right; i++)
        {
            if(a[min]>a[i])
            min=i;
            if(a[i]>a[max])
            max=i;
        }
        Swap(&a[left],&a[min]);
        //极值在两端，可能会换两次
        if(max==left)
        {
            max= min;
        }
        Swap(&a[right],&a[max]);
        left++;
        right--;
    }
}

//快速排序：双指针+递归
void FastSort(int *a, int start, int end)
{
    if(start>=end)
    return;

    int left= start;
    int right= end;
    int temp= a[left]; //将最左边的值定位基准值
    while(left<right)
    {
        //右边往左动找比基准值小的数
        while (a[right]> temp && left<right)
        right--;
            
            if(left<right)
            {
            a[left]=a[right];
            left++;
            }   //把右边的比基准值小的数，扔到左边
        
        
        //左边往右边动找比基准值大的数
        while (a[left]<temp && left<right)
        left++;
            
            if(left<right)
            a[right--]= a[left]; //把左边的比基准值大的数扔到右边
    }
                a[left]=temp;
            FastSort(a,start,left-1);
            FastSort(a,right+1,end);
}

int BinarySearch(int *a, int size, int element)
{
    int left=0;
    int right= size-1;
    while(left<=right)
    {
        int mid= left+(right-left)/2;
        // int mid= (left & right) + ((left ^ right)>>1);
    
    if(a[mid]>element)
    {
        right= mid-1;
    }
    else if(a[mid]<element)
    {
        left= mid+1;
    }
    else
    {
        return mid;
    }
    }
    return -1;
}

int main()
{
    int a[6]={16,13,3,1,23,41};
    // BubbleSort(a,5);
    // PrintArray(a,5);
    // InsertSort(a,5);
    // ChooseSort(a,5);
    // ChooseSort2(a,5);
    FastSort(a,0,5);
    PrintArray(a,6);

    printf("%d\n",BinarySearch(a,6,15));
    return 0;
}